<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>图示</title>
</head>
<style>
    p {
        text-align: center;
    }

    .left {
        background-color: aqua;
    }

    .mid {
        color: blueviolet;
        background-color: red;
    }

    .right {
        background-color: orange;
    }
</style>

<body>
    <p><span class="left">较小的</span> <span class="mid">基准数</span> <span class="right">较大的</span></p>
    <p> 1,3,7,4,2,4,20,39,25,21,90</p>
    <p>

        <svg width="60px" viewBox="0 0 60 35" version="1.1" xmlns="http://www.w3.org/2000/svg"
            xmlns:xlink="http://www.w3.org/1999/xlink">
            <path d="m20 2
        v20 h-10
        l15 10 l15 -10 
        h-10 v-20 
        h-10 " fill="none" stroke="#0ff" stroke-width="1" />
        </svg>
    </p>
    <p> <span class="orange left">1,3,7,4,2,4,</span> <b class="mid">20</b> <span class="right">39,25,21,90</span></p>
    <p>

        <svg width="60px" viewBox="0 0 60 35" version="1.1" xmlns="http://www.w3.org/2000/svg"
            xmlns:xlink="http://www.w3.org/1999/xlink">
            <path d="m20 2
        v20 h-10
        l15 10 l15 -10 
        h-10 v-20 
        h-10 " fill="none" stroke="#0ff" stroke-width="1" />
        </svg>
    </p>
    <p> <span class="left"><span class="left">1,2,3,</span><b class="mid">4,4</b> <span class="right">, 7</span> </span>
        &nbsp; <b class="mid">20</b>&nbsp; <span class="right"> <span class="left">21,</span><b class="mid">25</b><span
                class="right">,39,90</span></span></p>
</body>
<script>
    const arr = [1, 3, 5, 7, 2, 4, 6, 8], k = 4;
    /* 用i j表示待排序数组的开始结束索引  */
    let i = 0, len = arr.length, j = len - 1, time = 0;
    while (true) {
        time++
        
        let mid = arr[i]
        console.log(i, j, mid, 'i,j mid')
        /* n是左边第一个大于基准值的， m是右边第一个小于基准值的 */
        let n = i+1, m = j;
        let midInd = i ;
        while (n < m) {
            /* 基准值取得是第一位 ，当基准值后面数小于基准值时，移动基准值的索引 */
            while (arr[n] <= mid && n <= m) { n++ }
            while (arr[m] > mid && m >= n) { m-- }
            /* 下面这个判断就是防止 全部大于或者小于基准值的情况 */
            if( m < n){ 
                /* 这个时候基准值的索引有可能已经变了  所以n要从下一位开始*/
                if (n !== midInd) {
                    console.log(arr, midInd, n-1 , 'pre')
                    arr[midInd] = arr[n-1]
                    arr[n-1] = mid;
                    console.log(arr, midInd, n-1 , 'after')
                    midInd= n-1
}
                break;
             }
            let t = arr[n]
            arr[n] = arr[m]
            arr[m] = t
            /* 交换之后 n 就是左边最后一位 m就是右边第一位 */
            /* 为了让基准值在排序后面处于中央 我这种写法有问题，需要最后处理一下 把基准值和左边最后一位交换位置 */
            if (n!== midInd) {

            arr[midInd] = arr[n]
            arr[n] = mid;
            /* 交换之后要更新基准值的位置 */
            midInd = n
            }
            console.log(n, m, 'mn')
        }
 
        console.log(arr)

        /* i<k就可以排除已经有的左边部分了， i大于k ，就可以排除大于的右边部分了  */
        if (n === k) {
            break
        }
        if (n < k) {
            i = n
        } else {
            /* 大于的情况必须重选基准值 */
            j = n - 1
        }
        if (time > 20) { break }
    }
</script>

</html>